package problems;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import utils.Utils;

/**
 * Let S = {2, 3, 5, ..., 4999} be the set of prime numbers less than 5000.
 * 
 * Find the number of subsets of S, the sum of whose elements is a prime number.
 * Enter the rightmost 16 digits as your answer.
 * 
 * @author Jorn
 */
public class Problem249 {
	public static void main(String[] args) {
		List<Long> primes = new ArrayList<Long>(Utils.allPrimesUnder(5000));
		
		BigInteger counter = BigInteger.valueOf(primes.size()); //all single element subsets
		
		for (int setSize = 2; setSize < primes.size(); setSize++) {
//			System.out.println("List size is now " + setSize);
			for (List<Long> subset : Utils.subsets(primes, setSize)) {
				if (Utils.isPrime(Utils.sum(subset))) {
					counter = counter.add(BigInteger.ONE);
				}
			}
		}
		
		if (Utils.isPrime(Utils.sum(primes))) {
			counter = counter.add(BigInteger.ONE);
		}
		
		System.out.printf("Found %s subsets of primes%n", counter);
	}
}
